package primary.primary0;

import java.util.Arrays;


public class S0045跳跃游戏II {

    /**
     * 6
     * 贪心太难
     * 试下动态规划，递推
     * 从后往前 fi为从i跳到最后用的最小步数
     * fi = 1 + min(fi + 1， xxx ， fi+nums[i])
     */
    class Solution {
        public int jump(int[] nums) {
            int[] record = new int[nums.length];
            Arrays.fill(record, nums.length);
            record[nums.length - 1] = 0;
            for(int i = nums.length - 2; i >= 0; i--){
                for(int j = i + 1; j <= i + nums[i] && j < nums.length; j++){
                    record[i] = Math.min(record[i], record[j] + 1);
                }
            }
            return record[0];
        }
    }

    /**
     * 感觉贪心算法不说人话，我得翻译一下
     * 寻找每次跳跃能跳的最远的地方。
     * 如果step次最远跳到end，那么step+1次能跳到的最远的地方
     */
    public int jump5(int[] nums) {
        int totalLen = nums.length;
        // 当前步数
        int curStep = 0;
        // 当前步数能到达的最远距离
        int curStepEnd = 0;
        // 下一步能到达的最远距离
        int nextStepEnd = -1;

        for (int curLoc = 0; curLoc < totalLen; curLoc++) {
            // 寻找下一步能到达的最远距离
            nextStepEnd = Math.max(nextStepEnd, curLoc + nums[curLoc]);
            if(curLoc == curStepEnd){
                // 走到头了。
                curStep ++;
                curStepEnd = nextStepEnd;
                // 注意这时候再往下的时候，如果本来curStep = 1，curStepEnd = 3,nextStepEnd = 10;
                // 那么我们寻找下一组的时候，是在 3 - 10中间，寻找第三步最远能跑多远。
                // 第三步最远为啥和0-3这几个节点没关系了呢?因为上一步肯定在3-10之间!!有点拗口。
            }

        }
        return curStep;
    }

    /**
     * 贪心算法，是动态规划的一种。
     * 在出现 最少，最多 的条件下，可以使用。
     * 贪心教程: https://blog.csdn.net/qq_32400847/article/details/51336300
     */
    public int jump4(int[] nums) {
        int length = nums.length;
        // 当前次数能跳到的最远的地方
        int end = 0;
        //
        int maxPosition = 0;
        // 跳跃次数
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            // 因为下面有个i==end的切换条件，所以这句话可以认为是在寻找 end 范围之内，step + 1次跳跃，能跳到的最远的地方
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                // 遍历到end了，现在maxPosition是step次跳远能跳到的最远的地方。于是我们需要寻找step+1次跳跃能跳到的最远的地方
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    /**
     * 9
     * 从后往前，动态规划应该比较简单
     * 同样的方法从前到后走dfs应该也差不多
     */
    public int jump(int[] nums) {
        int[] record = new int[nums.length];
        Arrays.fill(record, record.length - 1);
        record[nums.length - 1] = 0;
        // mark: 二维数组怎么创建的来着
        // 最后一个不考虑
        for(int i = nums.length - 2; i >= 0; i--){
            for(int j = i + 1; j <= i + nums[i] && j <= nums.length - 1; j++){
                record[i] = Math.min(record[j] + 1, record[i]);
            }
        }
        return record[0];
    }

    /**
     * 另一个做法，也不太行。
     */
    public int jump2(int[] nums) {
        // 上一个节点的位置
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            // 从左到右找第一个能抵达上一个节点的下一个节点
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    /*
     * dfs试一把喽
     * 不知道咋剪枝，指数爆炸了，超时
     */
    public int jump3(int[] nums) {
        int[] record = new int[nums.length];
        Arrays.fill(record, record.length);
        findMinCount(record, nums, 0, 0);
        return record[record.length - 1] - 1;
    }
    public void findMinCount(int[] record, int[] nums, int curLoc, int preCount){
        if(curLoc >= nums.length){
            return;
        }
        record[curLoc] = Math.min(record[curLoc], preCount + 1);
        for(int i = 1; i <= nums[curLoc]; i++){
            findMinCount(record, nums, curLoc + i, record[curLoc]);
        }

    }
}
